﻿

class BoardIssue
{
    // 电路板数量
    private int[] Boards;
    // 连接块数量
    private int[][] ConNode;
    private int BestRes;
    private List<List<int>> ResSpace = new List<List<int>>();
    private void AddCB(params int[] p)
    {
        int i = 0;
        while (ConNode[i] != null && i < ConNode.Count())
            i++;
        ConNode[i] = new int[p.Count()];
        for (int j = 0; j < p.Count(); j++)
            ConNode[i][j] = p[j];
    }

    public bool isConnected(int bnum, int n)
    {
        for (int i = 0; i < ConNode[n].Count(); i++)
            if (bnum == ConNode[n][i])
                return true;
        return false;
    }

    private void Showout(List<int> Container)
    {
        Console.WriteLine("---------------------");
        for (int i = 0; i < Container.Count(); i++)
            Console.Write($"{Container[i],3}");
        Console.Write("\n");
        for (int i = 0; i < ConNode.Count(); i++)
        {
            for (int j = 0; j < Container.Count(); j++)
            {
                if (isConnected(Container[j], i))
                {
                    Console.Write("  x");
                }
                else
                    Console.Write("   ");
            }
            Console.Write("\n");
        }
        Console.WriteLine("---------------------");
    }

    public BoardIssue(int Boards, int ConnectBlocks)
    {
        this.Boards = new int[Boards];
        ConNode = new int[ConnectBlocks][];
        BestRes = 0;

        for (int i = 0; i < this.Boards.Count(); i++)
            this.Boards[i] = i + 1;
    }


    /// <param name="num"> 要插入的板子编号 </param>
    /// <returns> 返回预计的密度 </returns>
    private int PredictRes(int num, List<int> C)
    {
        int res = 0;
        C.Add(num);
        foreach (var Ni in ConNode)
        {
            int cnt = Ni.Count();
            foreach (var i in C)
            {
                if (Ni.Contains(i))
                    cnt--;
            }
            if (cnt != 0 && cnt != Ni.Count())
                res++;
        }
        C.Remove(num);

        return res;
    }

    private int calcRes(List<int> Container)
    {
        List<int> temp = new List<int>();
        int res = 0;
        foreach (var Ci in Container)
        {
            res = Math.Max(PredictRes(Ci, temp), res);
            temp.Add(Ci);
        }
        return res;
    }
    struct LiveNodes
    {
        public List<int> C;
        public int curRes;
        public LiveNodes(List<int> container, int cres)
        {
            C = container;
            curRes = cres;
        }
    }
    /// <summary>
    /// 使用回溯法求
    /// </summary>
    private void SolveWithBackTrace()
    {
        LinkedList<LiveNodes> queue = new LinkedList<LiveNodes>();//创建队列
        List<int> tc = new List<int>();
        BestRes = FindBoundaryWithGreedy(tc);//
        // BestRes = int.MaxValue;
        queue.AddLast(new LiveNodes(tc, BestRes));

        do
        {
            if (queue.Last().C.Count() < Boards.Count())//如果节点还可以衍生
            {
                LiveNodes temp = new LiveNodes(queue.Last().C,queue.Last().curRes);
                queue.RemoveLast();
                if (temp.curRes <= BestRes)//只有当节点的当前小于全局最佳才可以继续生成子节点
                    foreach (var Bi in Boards)
                    {
                        if (!temp.C.Contains(Bi))//筛选出来还没有被排列的电路板
                        {
                            List<int> tC = new List<int>(temp.C);
                            tC.Add(Bi);
                            int curRes = calcRes(tC);
                            BestRes = Math.Min(FindBoundaryWithGreedy(tC), BestRes);//更新上界
                            if (curRes <= BestRes)//如果结果小于等于最佳那么保留
                            {
                                LiveNodes node = new LiveNodes(tC, curRes);
                                queue.AddLast(node);
                            }
                        }
                    }
            }
            else//如果无法再生成子节点
            {
                if (BestRes >= queue.Last().curRes)
                    ResSpace.Add(queue.Last().C);
                queue.RemoveLast();
            }
        } while (queue.Count() != 0);


    }

    ///<summary> 使用分支限界法求结果 </summary>
    /// 
    private void SolveWithBAB()
    {
        LinkedList<LiveNodes> queue = new LinkedList<LiveNodes>();//创建队列
        List<int> tc = new List<int>();
        BestRes = FindBoundaryWithGreedy(tc);//
        queue.AddLast(new LiveNodes(tc, BestRes));

        do
        {
            if (queue.First().C.Count() < Boards.Count())//如果节点还可以衍生
            {
                if (queue.First().curRes <= BestRes)//只有当节点的当前小于全局最佳才可以继续生成子节点//TODO 贪心法有问题
                    foreach (var Bi in Boards)
                    {
                        if (!queue.First().C.Contains(Bi))//筛选出来还没有被排列的电路板
                        {
                            List<int> tC = new List<int>(queue.First().C);
                            tC.Add(Bi);
                            int curRes = calcRes(tC);
                            BestRes = Math.Min(FindBoundaryWithGreedy(tC), BestRes);//更新上界
                            if (curRes <= BestRes)//如果结果小于等于最佳那么保留
                            {
                                LiveNodes node = new LiveNodes(tC, curRes);
                                queue.AddLast(node);
                            }
                        }
                    }
                queue.RemoveFirst();//将已经生成过子节点的节点出队
            }
            else//如果无法再生成子节点
            {
                if (BestRes >= queue.First().curRes)
                    ResSpace.Add(queue.First().C);
                queue.RemoveFirst();
            }
        } while (queue.Count() != 0);


    }
    /// <summary>
    /// 使用贪心法寻找边界
    /// </summary>
    /// <returns>
    /// 返回一个上界
    /// </returns>
    private int FindBoundaryWithGreedy(List<int> Container)
    {
        List<int> C = new List<int>(Container);
        for (int i = C.Count(); i < Boards.Count(); i++)
        {
            int minRes = int.MaxValue;
            int num = i + 1;
            foreach (int j in Boards)
            {
                if (!C.Contains(j))
                {
                    int res = PredictRes(j, C);
                    if (minRes > res)
                    {
                        minRes = res;
                        num = j;
                    }
                }
            }
            C.Add(num);
        }
        return calcRes(C);
    }

    private void SolveWithGreedy(List<int> Container)
    {
        for (int i = 0; i < Boards.Count(); i++)
        {
            int minRes = Boards.Count();
            int num = i + 1;
            foreach (int j in Boards)
            {
                if (!Container.Contains(j))
                {
                    int res = PredictRes(j, Container);
                    if (minRes > res)
                    {
                        minRes = res;
                        num = j;
                    }
                }
            }
            if (minRes > BestRes)
                BestRes = minRes;
            Container.Add(num);
            // Showout(Container);
            // Console.WriteLine($"get res:{BestRes}");
        }
    }

    static void Main()
    {
        BoardIssue issue = new BoardIssue(8, 5);
        issue.AddCB(1, 2);
        issue.AddCB(1, 3);
        issue.AddCB(3, 6);
        issue.AddCB(4, 5, 6);
        issue.AddCB(7, 8);

        // issue.AddCB(1,2,3);
        // issue.AddCB(2,3,4);
        // issue.AddCB(2,3,4,5);
        // issue.AddCB(4,5,6);
        // issue.AddCB(5,7);
        // issue.AddCB(5,7,8);
        // issue.AddCB(7, 8, 9);
        // issue.AddCB(8, 9, 10, 11);

        // Console.WriteLine($"{issue.PredictRes(1)}");
        System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
        stopwatch.Start();
        issue.SolveWithBAB();
        // issue.SolveWithBackTrace();
        stopwatch.Stop();
        TimeSpan timeSpan = stopwatch.Elapsed;
        // issue.Showout(issue.ResSpace[issue.ResSpace.Count() - 1]);
        Console.WriteLine($"BestRes:{issue.BestRes},Solutions:{issue.ResSpace.Count()}");
        Console.WriteLine($"Time Cost:{timeSpan.TotalMilliseconds}");
    }
}